package com.matt.binarytree;

public class BinaryTree {
	
	public Node root;
	
	/**
	 * Method to insert a Node into binary tree.
	 * @param newNode Node to be inserted.
	 */
	private void insert(Node newNode) {
		if(root == null) {
			root = newNode;
		} else {
			Node curNode = root;
			Node parent;
			
			while(true) {
				parent = curNode;
				
				if(newNode.key < curNode.key) {
					curNode = curNode.leftChild;
					
					if(curNode == null) {
						curNode = newNode;
						return;
					}
				} else {
					curNode = curNode.rightChild;
					
					if(curNode == null) {
						curNode = newNode;
						return;
					}
				}
			}
			
		}
	}
	
	/**
	 * Method to delete a node from a binary tree.
	 * @param node Node to be deleted.
	 */
	private void delete(Node node) {
		
	}
	
	/**
	 * Method to find a Node.
	 * @param node Node to be found.
	 * @return Node
	 */
	private Node findNode(Node node) {
		Node curNode = root;
		
		while(curNode.key != node.key) {
			if(node.key < curNode.key) {
				curNode = curNode.leftChild;
			} else {
				curNode = curNode.rightChild;
			}
			
			if(curNode == null)
				return null;
		}
		
		return curNode;
	}
	
	/**
	 * Add a new Node to the binary tree.
	 * @param node Node to be added.
	 */
	private void addNode(Node node) {
		
		if(root == null) {
			root = new Node(node.key, node.employeeName);
		}
		else
		{
			Node curNode = root;
			Node parent;
			
			while(true) {
				parent = curNode;
				
				if(node.key < parent.key) {
					curNode = curNode.leftChild;
					
					if(curNode == null) {
						parent.leftChild = node;
						return;
					}
					
				} else {
					
					curNode = curNode.rightChild;
					
					if(curNode == null) {
						parent.rightChild = node;
						return;
					}
					
				}
			}
		}
		
	}
	
	public void inOrderTraversal(Node node) {
		
		if(node != null) {
			inOrderTraversal(node.leftChild);
			
			System.out.print(node + "\n");
			
			inOrderTraversal(node.rightChild);
		}
		
	}
	
	
	public static void main(String[] args) {
		
		BinaryTree binaryTree = new BinaryTree();
		
		Node aubry = new Node(100, "Aubry");
		Node jeff = new Node(2, "Jeff");
		Node ted = new Node(15, "Ted");
		Node zack = new Node(78, "Zack");
		Node sue = new Node(132, "Sue");
		Node matt = new Node(5, "Matt");
		
		Node insertNode = new Node(3, "Jason");
		
		binaryTree.addNode(matt);
		binaryTree.addNode(jeff);
		binaryTree.addNode(aubry);
		binaryTree.addNode(ted);
		binaryTree.addNode(zack);
		binaryTree.addNode(sue);
		
		binaryTree.inOrderTraversal(matt);
		binaryTree.insert(insertNode);
		binaryTree.inOrderTraversal(matt);
		
		System.out.println("Searching for key 78:");
		System.out.println(binaryTree.findNode(zack));
		
	}

}
